{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Import word2vec\n",
    "from gensim.models import Word2Vec\n",
    "\n",
    "# Define Neo4j connections\n",
    "from neo4j import GraphDatabase\n",
    "import pandas as pd\n",
    "\n",
    "host = 'bolt://localhost:7687'\n",
    "user = 'neo4j'\n",
    "password = 'letmein'\n",
    "driver = GraphDatabase.driver(host,auth=(user, password))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph import\n",
    "\n",
    "Today we will be using the Spoonacular Food Dataset that is available on Kaggle. It contains nutritional information alongside the ingredients used in 1600+ dishes. Unfortunately, it contains no recipe for sourdough bread.\n",
    "\n",
    "There are three types of nodes in our graph schema. A dish consists of one or more ingredients, which we represent as a connection between a dish and its ingredients. Recipes fall into categories or types such as lunch, breakfast, and so on.\n",
    "We use the <code>apoc.schema.assert</code> procedure to define the graph schema. It allows us to describe multiple indexes and unique constraints in a single query.\n",
    "\n",
    "Before we can execute the import query, we have to download the dataset and copy it to the Neo4j import folder. In the import query, we do a tiny bit of preprocessing as we lowercase the names of ingredients and replace dash characters (-) with whitespace."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph_schema_query = \"\"\"\n",
    "\n",
    "CALL apoc.schema.assert( \n",
    "    // define indexes \n",
    "    null, \n",
    "    // define unique constraints \n",
    "    {Ingredient:['name'], Dish:['id'], DishType:['name']})\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "graph_import_query = \"\"\"\n",
    "\n",
    "LOAD CSV WITH HEADERS FROM \"file:///newfood.csv\" as row \n",
    "CREATE (d:Dish{id:row.id}) \n",
    "SET d += apoc.map.clean(row, ['id','dishTypes','ingredients'],[]) \n",
    "FOREACH (i in split(row.ingredients,',') | MERGE (in:Ingredient{name:toLower(replace(i,'-',' '))}) \n",
    "                                           MERGE (in)<-[:HAS_INGREDIENT]-(d)) \n",
    "FOREACH (dt in split(row.dishTypes,',')  | MERGE (dts:DishType{name:dt}) \n",
    "                                           MERGE (dts)<-[:DISH_TYPE]-(d))\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "with driver.session() as session:\n",
    "    session.run(graph_schema_query)\n",
    "    session.run(graph_import_query)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basic graph exploration\n",
    "\n",
    "To start off, we will do a bit of graph exploration. Let's look at which ingredients are used the most."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with driver.session() as session:\n",
    "    results = session.run(\"\"\"\n",
    "    MATCH (n:Ingredient)\n",
    "    RETURN n.name as ingredient, size((n)<--()) as mentions \n",
    "    ORDER BY mentions DESC\n",
    "    LIMIT 10\n",
    "    \"\"\")\n",
    "pd.DataFrame([dict(result) for result in results])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Olive oil is by far the most popular as it is used in more than half of the recipes. Slowly following are garlic, salt, and butter. I didn't know that butter was so popular. I also found it quite surprising that anchovies are so widely used. Or maybe the dataset is just biased towards dishes that contain anchovies.\n",
    "\n",
    "We could build an application on top of this dataset to search for recipes based on the desired ingredients we want to cook. I borrowed this cypher query from the What's cooking series written by Mark Needham and Lju Lazarevic. Let's say, for example, you want to eat zucchini and feta cheese today, but don't have any idea which recipe to go for. Luckily, our application could help us solve this problem with the following cypher query."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with driver.session() as session:\n",
    "    results = session.run(\"\"\"\n",
    "    WITH [\"feta cheese\", \"zucchini\"] as ingredients \n",
    "    MATCH (d:Dish) \n",
    "    WHERE all(i in ingredients WHERE exists( \n",
    "        (d)-[:HAS_INGREDIENT]->(:Ingredient {name: i}))) \n",
    "    RETURN d.title AS dish, \n",
    "           [(d)-[:HAS_INGREDIENT]->(i) | i.name] AS ingredients \n",
    "    ORDER BY size(ingredients)\n",
    "    LIMIT 10\n",
    "    \"\"\")\n",
    "pd.DataFrame([dict(result) for result in results])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could go with a salad or a fish. I think I'll pass and skip over to node2vec for dessert.\n",
    "\n",
    "## Node2vec algorithm\n",
    "\n",
    "The node2vec algorithm is relatively new. It was proposed only in the year 2016 by Jure Leskovac and Aditya Grover in an article node2vec: Scalable Feature Learning for Networks. To understand how it works, we must first understand the word2vec algorithm. Word2vec algorithm was proposed in the year 2013 by a team of researchers led by Tomas Mikolov at Google. It is a popular technique using neural networks to learn the word embedding. It takes a list of sentences as input and produces a vector or an embedding for each word that appears in the text corpus. Words with similar meanings should be closer in the embedding space. For example, apple and pear should be more similar than apple and car. There are two training algorithms for word2vec. The first method is called the continuous bag of words (CBOW), which uses the context of the word to predict a target term. The context is defined as words that appear near the target word in the text. The second method is called skip-gram. Instead of trying to predict the target word from the context, it tries to predict the context of a given term. If you want to learn more about the word2vec algorithm, there is plenty of good literature about it on the internet.\n",
    "\n",
    "\n",
    "You might ask how we get from word2vec to node2vec. It is actually straightforward. Instead of using a list of sentences as input, we use a list of random walks. This is the only difference.\n",
    "\n",
    "## Neo4j Graph Data Science library\n",
    "\n",
    "Neo4j Graph Data Science library supports the random walk algorithm, which makes it very easy for us to implement the node2vec algorithm. If you need a quick refresher on how the GDS library works, you can check out my previous blog post. We will start by projecting the in-memory graph. We describe all three node labels and project relationships as undirected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with driver.session() as session:\n",
    "    session.run(\"\"\"CALL gds.graph.create('all', \n",
    "    '*', \n",
    "    {ALL_UNDIRECTED: {type:'*', orientation:'UNDIRECTED'}})\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we are ready to train our first node2vec model. The process will consist of three parts:\n",
    "\n",
    "Execute the random walk algorithm starting from each node in the graph\n",
    "Feed the random walks to word2vec algorithm\n",
    "Inspect results by looking at the most similar neighbors\n",
    "\n",
    "The random walk algorithm has an optional start parameter, which can be used to define the starting node of the walk. We can also specify how long the walk should be with the steps setting and how many times it should be repeated with the walks parameter. Note that every time random walk is executed, we expect a different result.\n",
    "\n",
    "We will use the Word2vec algorithm implementation in the gensim library. It also has a couple of hyperparameters we can define. Most notable are:\n",
    "\n",
    "* size: Dimensionality of the embedding vectors\n",
    "* window: Maximum distance between the current and predicted word\n",
    "* min_count: The minimum count of words to consider when training the model; words with occurrence less than this count will be ignored.\n",
    "* sg: The training algorithm: 1 for skip-gram; otherwise default CBOW\n",
    "\n",
    "Check out the official documentation for more information about the word2vec hyperparameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define random walk query\n",
    "random_walks_query = \"\"\"\n",
    "\n",
    "MATCH (node)\n",
    "CALL gds.alpha.randomWalk.stream('all', {\n",
    "  start: id(node),\n",
    "  steps: 15,\n",
    "  walks: 5\n",
    "})\n",
    "YIELD nodeIds\n",
    "// Return the names or the titles\n",
    "RETURN [id in nodeIds | \n",
    "    coalesce(gds.util.asNode(id).name, \n",
    "             gds.util.asNode(id).title)] as walks\n",
    "\n",
    "\"\"\"\n",
    "# Fetch data from Neo4j\n",
    "with driver.session() as session:\n",
    "    walks = session.run(random_walks_query)\n",
    "# Train the word2vec model\n",
    "clean_walks = [row['walks'] for row in walks]\n",
    "model = Word2Vec(clean_walks, sg=1, window=5, size=100)\n",
    "# Inspect results\n",
    "model.most_similar('olive oil')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If I knew it was that easy, I would have written about the node2vec algorithm before. On the other hand, the results smell kind of fishy. I have no idea what is it with this dataset and anchovies. It seems like the recipes were mostly written by someone who really likes them. You will probably get quite different results though.\n",
    "\n",
    "In the original node2vec paper, the authors defined two parameters that control the random walks execution. The first one is the return parameter.\n",
    "\n",
    ">Return parameter, p. Parameter p controls the likelihood of immediately revisiting a node in the walk. Setting it to a high value (> max(q, 1)) ensures that we are less likely to sample an already visited node in the following two steps (unless the next node in the walk had no other neighbor). This strategy encourages moderate exploration and avoids 2-hop redundancy in sampling. On the other hand, if p is low (< min(q, 1)), it would lead the walk to backtrack a step (Figure 2) and this would keep the walk “local” close to the starting node u.\n",
    "\n",
    "And the second parameter is called the in-out parameter.\n",
    "\n",
    ">In-out parameter, q. Parameter q allows the search to differentiate between “inward” and “outward” nodes. Going back to Figure 2, if q > 1, the random walk is biased towards nodes close to node t. Such walks obtain a local view of the underlying graph with respect to the start node in the walk and approximate BFS behavior in the sense that our samples comprise of nodes within a small locality. In contrast, if q < 1, the walk is more inclined to visit nodes which are further away from the node t. Such behavior is reflective of DFS which encourages outward exploration. However, an essential difference here is that we achieve DFS-like exploration within the random walk framework. Hence, the sampled nodes are not at strictly increasing distances from a given source node u, but in turn, we benefit from tractable preprocessing and superior sampling efficiency of random walks. Note that by setting πv,x to be a function of the preceeding node in the walk t, the random walks are 2nd order Markovian.\n",
    "\n",
    "In summary, the return parameter directs how often random walk backtracks a step or two. The in-out parameter controls if the random walk is more focused on local exploration, similar to BFS, or inclined more towards outward exploration like the DFS. Even though the random walk algorithm is still in the alpha tier, it supports these two node2vec parameters. Let's try them out in practice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define random walk query\n",
    "random_walks_query = \"\"\"\n",
    "\n",
    "MATCH (node)\n",
    "CALL gds.alpha.randomWalk.stream('all', {\n",
    "  start: id(node),\n",
    "  steps: 15,\n",
    "  walks: 5,\n",
    "  // define randomwalk node2vec params\n",
    "  mode:'node2vec',\n",
    "  inOut:0.6,\n",
    "  return:1.0\n",
    "})\n",
    "YIELD nodeIds\n",
    "// return name or title\n",
    "RETURN [id in nodeIds | \n",
    "    coalesce(gds.util.asNode(id).name, \n",
    "             gds.util.asNode(id).title)] as walks\n",
    "\n",
    "\"\"\"\n",
    "# Fetch data from neo4j\n",
    "with driver.session() as session:\n",
    "    walks = session.run(random_walks_query)\n",
    "# Train the word2vec model\n",
    "clean_walks = [row['walks'] for row in walks]\n",
    "model = Word2Vec(clean_walks, sg=1, window=5, size=100)\n",
    "model.most_similar('olive oil')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looking at results makes me hungry. It is really hard to say if the leg of lamb and olive oil should be regarded as similar ingredients. If we inspect the graph, out of eight recipes that include the leg of lamb, seven of those also use olive oil. By this logic, they are quite similar.\n",
    "\n",
    "In our next example, we will show how to run the node2vec algorithm and store the result embeddings back to Neo4j. Instead of returning the titles of dishes and ingredients, we will return the internal Neo4j node ids. This will help us to link the results back to Neo4j efficiently."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define random walk query\n",
    "random_walks_query = \"\"\"\n",
    "\n",
    "MATCH (node)\n",
    "CALL gds.alpha.randomWalk.stream('all', {\n",
    "  start: id(node),\n",
    "  steps: 15,\n",
    "  walks: 5,\n",
    "  mode:'node2vec',\n",
    "  inOut:0.6,\n",
    "  return:1.0\n",
    "})\n",
    "YIELD nodeIds\n",
    "// return the string of internal ID of nodes\n",
    "RETURN [id in nodeIds | toString(id)] as walks\n",
    "\n",
    "\"\"\"\n",
    "# fetch data from Neo4j\n",
    "with driver.session() as session:\n",
    "    walks = session.run(random_walks_query)\n",
    "# Train model\n",
    "clean_walks = [row['walks'] for row in walks]\n",
    "model = Word2Vec(clean_walks, window=5, size=100, sg=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The embeddings are now available in the vocabulary of the word2vec model. We will store them to Neo4j in a single batch using the <code>UNWIND</code> cypher statement. If possible, try to avoid committing a single transaction per row as this is not very performant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "store_embedding = \"\"\"\n",
    "UNWIND $data as row\n",
    "MATCH (n)\n",
    "WHERE id(n) = row.id\n",
    "SET n.embedding = row.embedding\n",
    "\"\"\"\n",
    "embeddings = []\n",
    "with driver.session() as session:\n",
    "    for record in model.wv.vocab:\n",
    "        id = record\n",
    "        # Prepare data\n",
    "        embeddings.append({'id':int(id), 'embedding': [float(x) for x in list(model.wv[id])]})\n",
    "    # Store embeddings to Neo4j    \n",
    "    session.run(store_embedding, {'data': embeddings})\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Word2vec model uses the cosine similarity to find the most similar words. The Graph Data Science library also supports the Cosine similarity algorithm, which can be used to infer a similarity algorithm. As with all similarity algorithms, we have to fine-tune the <code>similarityCutoff</code> and <code>topK</code> parameters to get the best results. They directly influence how sparse the inferred similarity graph will be."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cosine_similarity_algorithm = \"\"\"\n",
    "\n",
    "MATCH (node) \n",
    "WITH id(node) as id, node.embedding as weights \n",
    "WITH {item:id, weights: weights} as dishData \n",
    "WITH collect(dishData) as data \n",
    "CALL gds.alpha.similarity.cosine.write({\n",
    "    nodeProjection: '*', \n",
    "    relationshipProjection: '*', \n",
    "    similarityCutoff:0.5, \n",
    "    topK:5, \n",
    "    data: data,\n",
    "    writeRelationshipType:'COSINE_SIMILARITY'}) \n",
    "YIELD nodes, similarityPairs \n",
    "RETURN nodes, similarityPairs\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "with driver.session() as session:\n",
    "    results = session.run(cosine_similarity_algorithm)\n",
    "pd.DataFrame([dict(result) for result in results])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To finish this analysis, we will inspect the community structure of the inferred network with the label propagation algorithm. As we are only interested in a rough outline of the community structure, we can use the stats mode of the algorithm to provide us some basic community structure statistics."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with driver.session() as session:\n",
    "    results = session.run(\"\"\"CALL gds.labelPropagation.stats({\n",
    "                            nodeProjection:'*',\n",
    "                            relationshipProjection:'COSINE_SIMILARITY',\n",
    "                            maxIterations:20})\n",
    "                            YIELD communityCount, communityDistribution\n",
    "                            RETURN communityCount,\n",
    "                            apoc.math.round(communityDistribution.p50,2) as p50,\n",
    "                            apoc.math.round(communityDistribution.p75,2) as p75,\n",
    "                            apoc.math.round(communityDistribution.p90,2) as p90,\n",
    "                            apoc.math.round(communityDistribution.p90,2) as p95,\n",
    "                            apoc.math.round(communityDistribution.mean,2) as mean,\n",
    "                            apoc.math.round(communityDistribution.max,2) as max\"\"\")\n",
    "pd.DataFrame([dict(result) for result in results])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The label propagation algorithm found 123 groups in the similarity network. Most of them have less than 40 members. There are a handful of massive communities with the largest containing 625 members.\n",
    "\n",
    "## Conclusion\n",
    "\n",
    "The node2vec algorithm is a useful way of learning low-dimensional representations of the nodes in a graph that can be used downstream in a machine learning pipeline. During this blog post, I realized that changing the random walk algorithm parameters as well as the word2vec hyperparameters can produce very different results. Play around with them and see what works best for you."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "scispacy",
   "language": "python",
   "name": "scispacy"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
